package DataStructure.arrayAndList.doublePoint;

import java.util.Arrays;

/**
 * @author liujun
 * @version 1.0
 * @date 2021/07/26
 * @author—Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 三数之和
 * 给定一个数 target，在一维数组中，找出某 3 个数相加与 target最相近。
 * 要求：
 * 如果存在这个 3 个数，返回这三个数，没有返回{Integer.MIN_VALUE,Integer.MIN_VALUE,Integer.MIN_VALUE}
 * 输入：
 * int[] demoArray01_y = {1, 100, 22, 39, 43, 58, 64, 76, 79, 85, 96, 58};
 * int target01 = 99;
 * 输出：true (1-22-76)
 */

public class ThreeSumLikely {

    public int[] getValues(int[] array, int target) {
        int[] answer = new int[]{Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE};
        if (array.length < 3) {
            return answer;
        }
        Arrays.sort(array);
        answer[0] = array[0];
        answer[1] = array[1];
        answer[2] = array[2];
        int temp = array[0] + array[1] + array[2] - target;

        for (int i = 0; i <= array.length - 3; i++) {
            int left = i + 1;
            int right = array.length - 1;
            while (left < right) {
                int tempSum = array[left] + array[right] + array[i] - target;
                if (Math.abs(temp) < Math.abs(tempSum)) {
                    break;
                } else {
                    temp = tempSum;
                    answer[0] = array[i];
                    answer[1] = array[left];
                    answer[2] = array[right];
                }
                if (tempSum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        Arrays.sort(answer);
        return answer;
    }
}
